package lc2;
import java.util.*;
import org.junit.*;

import util.BracketUtils;
public class Ex354 {

    class Solution {
        public int maxEnvelopes(int[][] nums) {
            int n = nums.length;
            
            Arrays.sort(nums, (n1, n2) -> {
                if (n1[0] == n2[0]) {
                    return n1[1] - n2[1];
                } else {
                    return n1[0] - n2[0];
                }
            });
    
            Queue<Node> queue = new PriorityQueue<>();
    
            Node cur = new Node(nums[0], 1);
            queue.offer(cur);
            int res = 1;
    
            for (int i = 1; i < nums.length; i++) {
                Node last = queue.peek();
                if (last.arr[0] < nums[i][0] && last.arr[1] < nums[i][1]) {
                    queue.poll();
                    Node node = new Node(nums[i], last.times + 1);
                    queue.offer(node);
                    res = Math.max(node.times, res);
                } else {
                    queue.offer(new Node(nums[i], 1));
                }
            }
    
            return res;
        }
    }
    
    class Node implements Comparable<Node> {
        int[] arr;
        int times;
        
        public Node(int[] arr, int times) {
            this.arr = arr;
            this.times = times;
        }
    
        @Override
        public int compareTo(Node node2) {
            Node node1 = this;
            int[] n1 = node1.arr, n2 = node2.arr;
            if (n1[0] == n2[0]) {
                return n1[1] - n2[1];
            } else {
                return n1[0] - n2[0];
            }
        }
    }
    

    @Test
    public void test() {
        Solution s = new Solution();

        int[][] nums = BracketUtils.to2DArray("[[4,5],[4,6],[6,7],[2,3],[1,1],[1,1]]");
        System.out.println(s.maxEnvelopes(nums));
    }

    
}
